package gailv.sherwood;

import java.util.Random;

/**
 * 舍伍德算法 随机洗牌
 * @author 米饭好好吃
 */
public class Sherwood {

    private final Random random = new Random();

    /**
     * 随机洗牌（打乱arr元素）
     * @param arr 数组
     * @param n 数组长度
     */
    public void shuffle(int[] arr, int n) {
        for (int i = n - 1; i > 0; i--) {
            int j = random.nextInt(i + 1); // 随机选取一个元素
            // 进行交换
            swap(arr, i, j);
            // 额外进行交换
            if (j > 0) {
                swap(arr, j, j - 1);
            }
        }
    }

    private void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
}
